package com.yun.algorithmproblem.leetcode;

import java.util.Arrays;

public class Leetcode1552 {

    public int maxDistance(int[] position, int m) {
        Arrays.sort(position);
        int left=1,right=(position[position.length-1]-position[0])/(m-1),ans=-1;
        while (left<=right){
            int mid=(left+right)>>1;
            if(check(mid,position,m)){
                ans=mid;
                left=mid+1;
            }else {
                right=mid-1;
            }
        }
        return ans;
    }

    private boolean check(int dis,int[] position,int m){
        int prev=position[0];
        int cnt=1;
        for (int i = 1; i < position.length; i++) {
            if(position[i]-prev>=dis){
                prev=position[i];
                cnt++;
            }
            if(cnt==m){
                return true;
            }
        }
        return false;
    }
}
